#include <string>
#include <sstream>
#include "Chain.h"

using std::string;

//--------------------------------------------------------------------------
// PushPermutations: Add permutation to end of list
// Parameters: 
// perm - permutation to add
// Assumes that perm is legal
//--------------------------------------------------------------------------
void Chain::PushPermutation(Permutation* perm)
{
	if (perm == NULL)
	{
		Debug::PrintDebugMsg("Trying to add NULL permutation to chain");
		return;
	}
	m_Permutations.push_back(perm);
}

//--------------------------------------------------------------------------
// PopPermutations: Removes last permutation added
// Returns: the permutation that was removed
//--------------------------------------------------------------------------
Permutation* Chain::PopPermutation()
{
	Permutation* perm = *(m_Permutations.end()-1);
	m_Permutations.pop_back();
	return perm;

}

//--------------------------------------------------------------------------
// IsLegalToAdd : Does perm have a small intersection with all 
//                permutations in chain and can be added
// Returns true if intersection between perm and all perms <= m_MaxIntersection
// and perm is not contained in any of the permutations in the chain
// Parameters:
// perm - Permutation to check
//--------------------------------------------------------------------------
bool Chain::IsLegalToAdd(const Permutation* perm) 
{
	vector<Permutation*>::iterator it;
	for (it = m_Permutations.begin();it < m_Permutations.end(); it++)
	{
		if (perm->GetName() == (*it)->GetName())
		{
			return false;
		}
		int intersectionSize = (*it)->CountIntersection(perm->GetMatrixRows(),perm->GetGroupSize());
		// Illegal permutations:
		// 1. more than max intersection
		// 2. Contain one of the matrices in the chain
		// 3. Are contained in one of the matrices in the chain
		if (intersectionSize > m_MaxIntersection || intersectionSize >= perm->GetGroupSize() || intersectionSize >= (*it)->GetGroupSize())
		{
			return false;
		}
	}
	return true;
}


//--------------------------------------------------------------------------
// Save 
// Saves chain to chain file
// 
// Parameters:
// wordLen - the length of the binary word
// wordWeight - the weight of the binary word
// fileNamePrefix - a prefix for the file name that will be crated.
//--------------------------------------------------------------------------
void Chain::Save(int wordLen, int wordWeight, string fileNamePrefix)
{
	string fileName = fileNamePrefix + "_" + m_Name;
	string fileEnding = ".chain";
	ChainWriter chainFile(fileName + fileEnding);

	chainFile.SetBinaryWordLength(wordLen);
	chainFile.SetBinaryWordWeight(wordWeight);
	chainFile.SetNumberOfGroups(m_Permutations.size());
	
	//prepare the group summary - an array of the group sizes in this chain.
	vector<Permutation*>::iterator it;
	int *groupSummary;
	try
	{
		groupSummary = new int[ m_Permutations.size()];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating group summary for save");
		throw(new GraphColoringException("memory allocation failed!"));
	}
	int i=0;
	for (it = m_Permutations.begin(); it < m_Permutations.end(); it++)
	{
		groupSummary[i] = (*it)->GetGroupSize();
		i++;
	}
	chainFile.SetGroupSummary("all groups sizes", groupSummary);

	//add the groups to the file (in the same order it was passed in the group Summary)
	//each group has a title that is the index of the group in the Summary.
	i=1;
	for (it = m_Permutations.begin(); it < m_Permutations.end(); it++)
	{
		vector<bool> **names = (*it)->GetAllVertexNames();
		if (names == NULL)
		{
			throw new GraphColoringException("Cannot get vertex names for group, cannot save output");
		}
		chainFile.SetFirstVertex(i, names[0]);
		for(int j=1; j < (*it)->GetGroupSize(); j++)
		{
			chainFile.SetNextVertex(names[j]);
		}
		i++;
		delete[] names;
	}

	delete[] groupSummary;

}

//--------------------------------------------------------------------------
// SaveForDebug
// creats a file with debug information about the chain that includes
// for each group in the chin it's related permutaions
//
// Parameters:
// wordLen  - the length of the binary word
// wordWeight - the weight of the binary word
// originalFileName  - the name of the file that contains this chain output
//--------------------------------------------------------------------------
#ifdef _DEBUG
void Chain::SaveForDebug(int wordLen, int wordWeight, string originalFileName)
{
	string fileEnding = ".debug";
	ChainWriter chainFile(originalFileName + fileEnding);
	
	chainFile.SetBinaryWordLength(wordLen);
	chainFile.SetBinaryWordWeight(wordWeight);
	chainFile.SetNumberOfGroups(m_Permutations.size());

	//prepare the group summary - an array of the group sizes in this chain.
	vector<Permutation*>::iterator it;
	int *groupSummary;
	try
	{
		groupSummary = new int[ m_Permutations.size()];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating group summary for save in debug");
		throw(new GraphColoringException("memory allocation failed!"));
	}
	int i=0;
	for (it = m_Permutations.begin(); it != m_Permutations.end(); it++)
	{
		groupSummary[i] = (*it)->GetGroupSize();
		i++;
	}
	chainFile.SetGroupSummary("all groups sizes", groupSummary);

	chainFile.SetGroupSummary("the groups (group title is it's name and not it's index)", NULL);
	//add the groups to the file, for each group also add it's related perms
	//note: the group title ("# n") is the group name and not it's  index in the group Summary.
	for (it = m_Permutations.begin(); it != m_Permutations.end(); it++)
	{
		vector<bool> **names = (*it)->GetAllVertexNames();
		if (names == NULL)
		{
			throw new GraphColoringException("Cannot get vertex names for group, cannot save output");
		}
		int groupName = (*it)->GetName();
		chainFile.SetFirstVertex(groupName, names[0]);
		for(int j=1; j < (*it)->GetGroupSize(); j++)
		{
			chainFile.SetNextVertex(names[j]);
		}

		//related perms:
		int *relatedPerms;
		try 
		{
			relatedPerms = new int[(*it)->GetRelatedPermsCount()];
		}
		catch(std::bad_alloc *e)
		{
			e = NULL; //to avoid compiler warning
			Debug::PrintDebugMsg("memory allocation failed  while saving related permuatations, skipping");
			continue;
		}

		vector<RelatedPermutation>::iterator relIt = (*it)->GetRelatedPermsBegin();
		int i = 0;
		for(; relIt != (*it)->GetRelatedPermsEnd(); relIt++)
		{
			relatedPerms[i] = relIt->GetIndex();
			i++;
		}
		chainFile.SetGroupSummary("related permutaions", relatedPerms);
	}
}
#endif

//--------------------------------------------------------------------------
// Clone: Create copy of chain
// Returns: deep copy of chain
//--------------------------------------------------------------------------
Chain *Chain::Clone()
{
	Chain *copy;
	try
	{
		copy = new Chain(m_MaxIntersection);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating new chain");
		return NULL;
	}

	vector<Permutation*>::iterator it;
	for (it= m_Permutations.begin(); it < m_Permutations.end(); it++)
	{
		// Clone each matrix and add to original
		Permutation *copyPerm = (*it)->Clone();
		if (copyPerm == NULL)
		{
			Debug::PrintDebugMsg("Cannot clone chain, one of the permutations cannot be copied");
			return NULL;
		}

		copy->PushPermutation(copyPerm);
	}
	return copy;
}	

//--------------------------------------------------------------------------
// RemoveIntersections: Removes intersections between permutations in chain
//						Intersection is removed from smaller group. Erases
//						empty groups.
//--------------------------------------------------------------------------
void Chain::RemoveIntersections()
{
	vector<Permutation*>::iterator it1, it2;
	
	for (size_t it1 = 0; it1 < m_Permutations.size(); it1++)
	{
		// Foreach matrix, go over the next matrices in the chain, check intersections and remove from the smaller one if needed
		for (size_t it2 = it1+1; it2 < m_Permutations.size(); it2++)
		{
			int intersectionSize = m_Permutations[it1]->CountIntersection(m_Permutations[it2]->GetMatrixRows(),m_Permutations[it2]->GetGroupSize());
			
			if (intersectionSize > 0)
			{
				Permutation *permToClean, *otherPerm;
				
				// Permutation 1 is bigger, remove from Permutation 2
				if ((m_Permutations[it1])->GetGroupSize() >= (m_Permutations[it2])->GetGroupSize())
				{
					permToClean = m_Permutations[it2];
					otherPerm = m_Permutations[it1];
				} else
				{
					// Permutation 2 is bigger, remove from Permutation 1
					permToClean = m_Permutations[it1];
					otherPerm = m_Permutations[it2];
				}

				int remainingSize = permToClean->GetGroupSize()-intersectionSize;
				// Update the matrix that was cleaned
				permToClean->UpdateMatrix(Permutation::GetMatrixWithoutIntersection(permToClean->GetMatrixRows(),permToClean->GetGroupSize(), 
					otherPerm->GetMatrixRows(), otherPerm->GetGroupSize(),intersectionSize), remainingSize);			
			}
		}	
	}

	// Now go over chain and remove all empty permutations
	vector<Permutation*>::iterator it = m_Permutations.begin();
	while (it < m_Permutations.end())
	{
		if ((*it)->GetGroupSize() == 0)
		{
			m_Permutations.erase(it);  // Erase empty permutation
			it = m_Permutations.begin(); // And restart search
		} else
		{
			it++;
		}
	}
}

//--------------------------------------------------------------------------
// Operator== : Chains are equal if their permutations are equal
//--------------------------------------------------------------------------
bool Chain::operator== (const Chain &other) const 
{

	if (this == &other)
	{
		return true;
	}

	if (m_Permutations.size() != other.GetLength())
	{
		return false;
	}

	for (size_t i = 0; i < m_Permutations.size(); i++)
	{
		bool found = false;
		vector<Permutation*> otherPerms = other.GetPermutations();
		for (vector<Permutation*>::iterator it = otherPerms.begin(); it < otherPerms.end() && !found; it++)
		{
			if (*(m_Permutations[i]) == *(*it))
			{
				found = true;
			}	
		}
		if (!found)
		{
			return false;
		}
	}

	return true;
}

//--------------------------------------------------------------------------
// Operator!= : Chains are equal if their permutations are equal
//-------------------------------------------------------------------------
bool Chain::operator!= (const Chain &other) const
{
	return !(*(this) == other);
}
